package Sort_Work;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * 快速排序（Hoare法、挖坑法、前后指针法）
 * 时间复杂度：
 *      最好：O(N^logN)
 *      最坏：O(N^@)
 * 空间复杂度：
 *      最好：O(logN)
 *      最坏：O(N)
 * 稳定性：不稳定
 */
public class Quick_Sort {
    //Hoare 法（未改进
//    public static void quickSort(int[] array) {
//        quick(array,0, array.length-1);
//    }
//    public static void quick(int[] array,int start,int end) {
//        if(start >= end) {
//            return;
//        }
//        //pivot是二者相遇的点 将基准与相遇点交换
//        int pivot = partition(array,start,end);
//        quick(array,start,pivot-1);
//        quick(array,pivot+1,end);
//    }
//    public static int partition(int[] array,int left,int right) {
//        int tmp = array[left];
//        int i = left;
//        while (left < right) {
//            while (left < right && array[right] >= tmp) {
//                right--;
//            }
//            while (left < right && array[left] <= tmp) {
//                left++;
//            }
//            swap(array,left,right);
//        }
//        swap(array,i,left);
//        return left;
//    }

    // 挖坑法 （未改进
//    public static void quickSort(int[] array) {
//        quick(array,0, array.length-1);
//    }
//    public static void quick(int[] array,int start,int end) {
//        if(start >= end) {
//            return;
//        }
//        //pivot是二者相遇的点 将基准与相遇点交换
//        int pivot = partition(array,start,end);
//        quick(array,start,pivot-1);
//        quick(array,pivot+1,end);
//    }
//    public static int partition(int[] array,int left,int right) {
//        int tmp = array[left];
//        while(left < right) {
//            while (left < right && array[right] >= tmp) {
//                right--;
//            }
//            array[left] = array[right];
//            while (left < right && array[left] <= tmp) {
//                left++;
//            }
//            array[right] = array[left];
//        }
//        array[left] = tmp;
//        return left;
//    }

    /////////////////////////// --- 快排的优化 --- //////////////////////////////////////////

    /**
     * 快排优化：1、三数取中法 可以有效避免出现单分支的情况
     *         2、递归到小的子区间时 可以考虑使用插入排序提升效率
     */
    public static void quickSort(int[] array) {
        quick(array,0, array.length-1);
    }
    public static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        //2、在一定区间内 使用直接插入排序 提升效率
        if(end-start+1 <= 10) {
            insertSort(array,start,end);
            return;
        }
        //1、三数取中    在找pivot之前 先找到中间数与第一个数交换作为基准
        int index = middleNum(array,start,end);
        swap(array,start,index);

        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    public static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while(left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    public static int middleNum (int[] array,int start,int end) {
        int mid = (start+end) / 2;
        if(array[start] > array[end]) {
            if(array[start] < array[mid]) {
                return start;
            } else if(array[end] > array[mid]) {
                return end;
            } else {
                return mid;
            }
        } else { //arrat[start] < array[end]
            if(array[start] > array[mid]) {
                return start;
            } else if(array[end] < array[mid]) {
                return end;
            } else {
                return mid;
            }
        }
    }

    public static void insertSort(int[] array,int start,int end) {
        for (int i = start; i <= end; i++) {
            int j = i - 1;
            int tmp = array[i];
            for (;j >= 0;j--) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                } else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    //快速排序的非递归实现
    public static void quickSortNor(int[] array) {
        int left = 0;
        int right = array.length-1;
        int pivot = partition(array,left,right);
        //把第一次划分的先存到栈中
        Stack<Integer> stack = new Stack<>();
        if(pivot - 1 > left) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot + 1 < right) {
            stack.push(pivot+1);
            stack.push(right);
        }

        while(!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);

            if(pivot - 1 > left) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot + 1 < right) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }
    /////////////////////////////////---测试区---////////////////////////////////
    public static void main(String[] args) {
        int[] array = new int[100];
        randomArray(array);
        //testQuickSort(array);
        quickSortNor(array);
        System.out.println(Arrays.toString(array));
    }

    //随机的样例
    public static void randomArray(int[] array) {
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            //数组长度范围内随机 也可以自定义
            array[i] = random.nextInt(array.length);
        }
    }

    public static void testQuickSort(int[] array) {
        int[] tmpArray = Arrays.copyOf(array, array.length);
        long startTime = System.currentTimeMillis();
        //调用你写的排序方法
        quickSort(tmpArray);
        long endTime = System.currentTimeMillis();
        System.out.println("快速排序花费的时间："+(endTime-startTime));
    }

    public static void swap(int[] array,int x,int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }
}
